#include <iostream>
using namespace std;

namespace ns_list
{
    class Node
    {
    public:
        Node(int val)
            : _val(val), _next(nullptr)
        {
        }

    public:
        int _val;
        Node *_next;
    };

    // 带头结点的链表
    class my_list
    {
    public:
        my_list()
            : phead(new Node(-1)), _size(0)
        {
        }
        Node *Find_by_Pos(int pos)
        {
            Node *cur = phead;
            while (cur && pos--)
            {
                cur = cur->_next;
            }
            return cur;
        }

        Node *Find_by_Val(int val = 0, int *count = nullptr)
        {
            Node *cur = phead->_next;
            while (cur && cur->_val != val)
            {
                if (count)
                    ++(*count);
                cur = cur->_next;
            }
            return cur;
        }

        bool InsertAfter(int pos, int val)
        {
            if (pos < 0 || pos > _size)
            {
                cerr << "输入的位置不合法" << endl;
                return false;
            }

            Node *node = new Node(val);
            if (!node)
            {
                cerr << "new 结点失败" << endl;
                return false;
            }

            Node *prev = Find_by_Pos(pos);
            if (!prev)
            {
                cerr << "找不到指定位置的节点" << endl;
                delete node;
                return false;
            }

            Node *next = prev->_next;

            // 连接前后结点
            prev->_next = node;
            node->_next = next;

            _size++;
            return true;
        }

        bool Erase(int val)
        {
            Node *curr = Find_by_Val(val);
            if (!curr)
            {
                cerr << "val 不存在!" << endl;
                return false;
            }

            Node *prev = phead;
            while (prev && prev->_next != curr)
            {
                prev = prev->_next;
            }
            if (!prev)
            {
                cerr << "找不到要删除节点的前驱节点" << endl;
                return false;
            }

            Node *next = curr->_next;

            // 删除并连接上
            delete curr;
            prev->_next = next;

            _size--;
            return true;
        }

        void PrintList()
        {
            Node *curr = phead->_next;
            while (curr)
            {
                cout << curr->_val << " ";
                curr = curr->_next;
            }
            cout << endl;
        }

        void Search(int val)
        {
            int count = 0;
            Node *result = Find_by_Val(val, &count);
            if (result)
            {
                cout << "找到啦，值为" << val << "，下标是#" << count << endl;
            }
            else
            {
                cout << "val 不存在!" << endl;
            }
        }

        void Push_Back(int val)
        {
            InsertAfter(_size,val);
        }

    private:
        Node *phead;
        int _size;
    };
};
